package main

import "fmt"

/*
![](http://cdn.bsummer.cn/20230804012751.png)
*/
func main() {
	fmt.Println(combine(4, 2))
}

//func combine(n int, k int) [][]int {
//	var res [][]int
//	var list []int
//	var helper func(n int, k int, list []int, startIndex int)
//	helper = func(n int, k int, list []int, startIndex int) {
//		if len(list) == k {
//			tmp := make([]int, len(list))
//			copy(tmp, list)
//			res = append(res, tmp)
//			return
//		}
//
//		// 剪枝操作放下这里效果一样
//
//		// for i:=startIndex;i<=n;i++{
//		for i := startIndex; i <= n; i++ {
//			// 剪枝操作
//			// k-len(list):装满list还需要的元素数
//			// n-i+1为最大还可以递归的次数(每次递归list元素数+1)
//			// 当n-i+1<k-len(list)时表明list元素数已经不可能补满了，直接跳出
//			if n-i+1 < k-len(list) {
//				break
//			}
//			list = append(list, i)
//			helper(n, k, list, i+1) // 第一点: 每深入一层递归，该层for起始index就等于上一个选取元素的索引位置+1
//			list = list[:len(list)-1]
//		}
//	}
//	helper(n, k, list, 1)
//	return res
//}

func combine(n int, k int) [][]int {
	res := [][]int{}
	list := []int{}

	var helper func(startIndex int)
	helper = func(startIndex int) {
		if len(list) == k {
			res = append(res, append([]int{}, list...))
			return
		}

		for i := startIndex; i <= n; i++ {
			if n-i+1 < k-len(list) {
				break
			}
			list = append(list, i)
			helper(startIndex + 1)
			list = list[:len(list)-1]
		}
	}
	helper(1)
	return res
}
